package LinkedList;

public class _148_SortList {
    //插入排序，超时
    public ListNode sortList_0(ListNode head) {
        ListNode begin = new ListNode(Integer.MIN_VALUE);
        while (head != null) {
            ListNode t1 = head.next;
            ListNode p = begin;
            while (p.next != null && p.next.val <= head.val) {
                p = p.next;
            }
            if (p.next == null) {
                p.next = head;
                head.next = null;
            } else if (p.next.val > head.val) {
                ListNode y = p.next;
                p.next = head;
                head.next = y;
            }
            head = t1;
        }
        return begin.next;
    }

    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(fast);
        return mergeSort(left, right);
    }

    //solution 2: use merge sort.
    public ListNode mergeSort(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeSort(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeSort(l1, l2.next);
            return l2;
        }
    }
}
